﻿#pragma once

using namespace std;
enum Colour
{
	BLACK,
	RED,
};


template<class K, class V>
struct RBTreeNode {
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(BLACK)
	{}
};
//1. 每个结点不是红色就是黑色
//2. 根节点是黑色的 
//3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 
//4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 
//5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
template<class K,class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;
public:

	void RotateL(Node*& parent)
	{
		Node* subR = parent->_right;
		Node* subR_L = subR->_left;
		Node* pphead = parent->_parent;

		parent->_right = subR_L;
		if (subR_L)
			subR_L->_parent = parent;
		
		subR->_left = parent;
		parent->_parent = subR;

		//处理subL的父节点
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = pphead;
			if (pphead->_left == parent)
			{
				pphead->_left = subR;
			}
			else if (pphead->_right == parent)
			{
				pphead->_right = subR;
			}
		}
	}


	void RotateR(Node*& parent)
	{
		Node* subL = parent->_left;
		Node* subL_R = subL->_right;
		Node* pphead = parent->_parent;

		parent->_left = subL_R;
		if (subL_R)
			subL_R->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = pphead;
			if (parent == pphead->_left)
				pphead->_left = subL;
			else if (parent == pphead->_right)
				pphead->_right = subL;
		}
	}

	bool insert(const pair<K,V>& kv)
	{
		//1.按搜索树的规则插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first == kv.first)
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < cur->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else if (parent->_kv.first > cur->_kv.first)
		{
			parent->_left = cur; 
			cur->_parent = parent;
		}

		//新插入的节点是黑色还是红色呢我们发现插入节点的时候只能破坏3，4规则
		//然后发现在插入新节点为红色的1时候只可能破坏连续两个节点都为红色的情况
		//相比于插入节点为黑色来说红色只会影响一条支路而插入一条黑色要影响每一条路
		cur->_col = RED;
		while (parent && parent->_col == RED) //如果父节点为空或者为黑就不要处理了
		{
			//是否需要调节要看叔叔节点
			//这里不需要判断 Gparent是否为空因为不可能为空
			//因为如果parent为红那么parent一定不会是根 不是根就一定会有祖父节点
			Node* Gparent = parent->_parent;
			//情况1uncle存在且为红
			//判断uncle节点是左节点还是右节点
			//情况2：cur为红，p为红，g为黑，u不存在/u存在且为黑 
			//p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
			//p为g的右孩子，cur为p的右孩子，则进行左单旋转
			//p、g变色--p变黑，g变红
			//情况3
			//p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
			//p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
			//cur变黑 g变红
			if (parent == Gparent->_left)
			{
				Node* uncle = Gparent->_right;
				if (uncle&&uncle->_col == RED) //情况1
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					Gparent->_col = RED;

					//继续往上处理
					cur = Gparent;
					parent = cur->_parent;
				}
				else //情况2或者3 在parent == Gparent->_left条件下
				{
					//因为parent已经是Gparent的左边了如果cur是parent的左边就是单旋
					//但因为无论是单旋还是多旋最后一个步骤都是单旋所以先处理多旋
					if (cur == parent->_right)
					{
						RotateL(parent);
						//因为多旋的情况下是cur变黑 而单旋的情况下是p变黑
						//所以这里直接交换相对位置 后面变色的时候处理就是一样的了
						swap(parent, cur);
					}

					//在处理单旋的情况了也就是情况2
					RotateR(Gparent);
					//在处理变色
					Gparent->_col = RED;
					//因为如果是双旋已经交换了所以这里的处理就同一了
					parent->_col = BLACK;

					break;
				}
			}
			else //parent为右子树
			{
				Node* uncle = Gparent->_left;
				if (uncle&&uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					Gparent->_col = RED;

					cur = Gparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(parent);
						swap(cur, parent);
					}

					RotateL(Gparent);
					Gparent->_col = RED;
					parent->_col = BLACK;
				}
				break;
			}




			//情况2 uncle不存在或者存在且为黑
		}

		_root->_col = BLACK;
		return true;
	}

	void _InOder(const Node* root)
	{
		if (root == nullptr)
			return;

		_InOder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOder(root->_right);
	}

		
	void InOder()
	{
		_InOder(_root);
		cout << endl;
	}


private:
	Node* _root = nullptr;
};